package q1260_shiftGrid;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    /*
    尝试用一个idx来进行定位 首先定位到k导致移动后 res中第一个path的第一个数应该在什么位置
    然后从这个位置一路添加数字直到全部都添加到res中即可
     */
    public List<List<Integer>> shiftGrid(int[][] grid, int k) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        // 首先k导致移动，那么此时不应该关注数组中第一个数移动到了哪里 而是应该关注移动后哪个数移到了第一个数的位置
        // 所以计算方法如下
        k = grid.length * grid[0].length - k % (grid.length * grid[0].length);
        int idx = k;
        // 然后用idx计算从这个数开始不断添加
        while (idx < grid.length * grid[0].length) {
            // i是计算idx对应数字所在行 j则是所在的列
            int i = idx / grid[0].length, j = idx % grid[0].length;
            path.add(grid[i][j]);
            if (path.size() == grid[0].length) {
                res.add(new ArrayList<>(path));
                path.clear();
            }
            ++idx;
        }
        idx = 0;
        while (idx < k) {
            int i = idx / grid[0].length, j = idx % grid[0].length;
            path.add(grid[i][j]);
            if (path.size() == grid[0].length) {
                res.add(new ArrayList<>(path));
                path.clear();
            }
            ++idx;
        }
        return res;
    }
}
